#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> nums;
    vector<int> choosen;

    vector<vector<int>> ans;
    unordered_map<int, int> m;

    int k;

    // 时间复杂度为 O(n * n!)，最坏的情况为全排列
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // 这里对每个数字出现的次数进行统计，
        // 并记录到一个新的不出现重复数字的数组
        for (int &n : nums) {
            if (m.find(n) == m.end()) {
                m[n] = 1;
                this->nums.push_back(n);
            } else {
                m[n] += 1;
            }
        }

        k = nums.size();
        permute();

        return ans;
    }

    void permute() {
        // 已经选择了 k 个数，那么记录下来
        if (choosen.size() == k) {
            ans.push_back(choosen);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // 这个数字已经被使用完了，不能再用了
            if (m[nums[i]] == 0) {
                continue;
            }

            // 用了就要将次数减一
            m[nums[i]] -= 1;
            choosen.push_back(nums[i]);

            permute();
            
            // 还原数字的使用次数和选择数字的数组
            choosen.pop_back();
            m[nums[i]] += 1;
        }
    }
};

int main() {
    vector<int> nums = {1, 1, 2};

    vector<vector<int>> results = Solution().permuteUnique(nums);

    for (auto& result : results) {
        cout << '[';

        for (int i = 0; i < result.size() - 1; i++) {
            cout << result[i] << ", ";
        }

        cout << result[result.size() - 1] << ']' << endl;
    }
    
    return 0;
}